/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * 思路简单，用堆，慢，超过 50% 的样子
 */

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  const heap = new MinHeap(lists.length, (ln, rn) => ln.val < rn.val);
  lists.forEach((ln) => {
    if (ln) heap.add(ln);
  });

  let head = null;
  let tail = null;

  while (heap.size > 0) {
    const minNode = heap.popMin();
    if (head === null) {
      head = minNode;
      tail = minNode;
    } else {
      tail.next = minNode;
      tail = minNode;
    }
    if (minNode.next !== null) {
      heap.add(minNode.next);
    }
  }

  return head;
};

/**
 * @param {number} capicity
 */
function MinHeap(capicity, lessThan) {
  this.elements = new Array(capicity);
  this.size = 0;
  this.lessThan = lessThan;
  this.leftIndex = (i) => i * 2 + 1;
  this.rightIndex = (i) => i * 2 + 2;
  this.parentIndex = (i) => Math.floor((i + 1) / 2 - 1);
  this.add = (e) => {
    this.elements[this.size] = e;
    this.up(this.size);
    this.size++;
  };
  this.up = (index) => {
    const current = this.elements[index];
    if (index === 0) return;
    const parentIndex = this.parentIndex(index);
    const parent = this.elements[parentIndex];
    if (this.lessThan(current, parent)) {
      this.elements[index] = parent;
      this.elements[parentIndex] = current;
      this.up(parentIndex);
    } else return;
  };

  this.popMin = () => {
    if (this.size === 0) return null;

    const min = this.elements[0];
    this.size--;
    const last = this.elements[this.size];
    this.elements[0] = last;
    this.down(0);
    return min;
  };
  this.down = (i) => {
    const e = this.elements[i];
    const l = this.leftIndex(i);
    const r = this.rightIndex(i);
    const hasLeft = l < this.size;
    const hasRight = r < this.size;
    if (!hasLeft && !hasRight) return;

    const le = this.elements[l];
    if (!hasRight) {
      /* hasleft only */
      this.tryDownLeft(i, l);
    } else {
      const re = this.elements[r];
      if (this.lessThan(le, re)) {
        this.tryDownLeft(i, l);
      } else {
        this.tryDownRight(i, r);
      }
    }
  };
  this.tryDownLeft = (i, l) => {
    const e = this.elements[i];
    const le = this.elements[l];
    if (this.lessThan(le, e)) {
      this.elements[l] = e;
      this.elements[i] = le;
      this.down(l);
    }
  };
  this.tryDownRight = (i, r) => {
    const e = this.elements[i];
    const re = this.elements[r];
    if (this.lessThan(re, e)) {
      this.elements[r] = e;
      this.elements[i] = re;
      this.down(r);
    }
  };
  this.toString = () => JSON.stringify(this.elements.slice(0, this.size)) + '; size=' + this.size;
}

// ------------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------

function ListNode(val, next = null) {
  this.val = val;
  this.next = next;
  this.toString = () => {
    const current = '' + this.val + ', ';
    const nextStr = this.next === null ? '' : this.next.toString();
    return current + nextStr;
  };
}

const kl = [
  new ListNode(1, new ListNode(4, new ListNode(5))),
  new ListNode(1, new ListNode(3, new ListNode(4))),
  new ListNode(2, new ListNode(6))
];

console.log(mergeKLists(kl).toString());
